package com.java.multipledatasource.algorithm;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

/**
 * @author hu
 * @version 1.0
 * @date 2021/1/25 0025 下午 7:06
 * @description
 */
public class Tree {

   static class TreeNode{
        private int value;
        private TreeNode left;
        private TreeNode right;

        public TreeNode(int value){
            this.value = value;
        }
    }

    /**
     * 二叉树先序遍历 （头 左 右）
     * @param treeNode
     */
    public static void midSort(TreeNode treeNode){
        if (treeNode != null) {
            System.out.print(treeNode.value + "   ");
            midSort(treeNode.left);
            midSort(treeNode.right);
        }
    }

    /**
     * 中序遍历 左右中
     * @param treeNode
     */
    public static void leftSort(TreeNode treeNode) {
        if (treeNode != null) {
            leftSort(treeNode.left);
            System.out.print(treeNode.value + "   ");
            leftSort(treeNode.right);
        }
    }

    /**
     * 后序 遍历 左右中
     * @param treeNode
     */
    public static void rightSort(TreeNode treeNode) {
        if (treeNode != null) {
            rightSort(treeNode.left);
            rightSort(treeNode.right);
            System.out.print(treeNode.value + "   ");
        }
    }

    /**
     * 宽度遍历
     * @param head
     */
    public static void widthSort(TreeNode head){
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(head);
        while (queue.size() > 0) {
            TreeNode poll = queue.poll();
            System.out.print(poll.value + " ");
            if (poll.left != null) {
                queue.add(poll.left);
            }
            if (poll.right != null) {
                queue.add(poll.right);
            }
        }
    }

    /**
     * 计算最大宽度
     * @param head
     * @return
     */
    public static int maxWidth(TreeNode head) {
        int max = 0;

        Map<TreeNode, Integer> map = new HashMap<>(16);
        int curLevel = 1; //当前所在层
        int curLevelNodes = 0; //当前层的节点数量

        map.put(head, curLevel);

        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(head);
        while (!queue.isEmpty()) {
            TreeNode curNode = queue.poll();
            Integer curNodeLevel = map.get(curNode);

            if (curNode.left != null) {
                queue.add(curNode.left);
                map.put(curNode.left, curNodeLevel + 1);
            }

            if (curNode.right != null) {
                map.put(curNode.right, curNodeLevel + 1);
                queue.add(curNode.right);
            }

            if (curLevel == curNodeLevel) {
                curLevelNodes++;
            } else {
                max = Math.max(max, curLevelNodes);
                curLevel++;
                curLevelNodes = 1;
            }
        }
        max = Math.max(max, curLevelNodes);
        return max;
    }

    /**
     * 二叉树 序列化
     * @param treeNode
     * @return
     */
    public static Queue<String> preSerial(TreeNode treeNode) {
        Queue<String> res = new LinkedList<>();
        pres(res, treeNode);
        return res;
    }

    public static void pres(Queue<String> res, TreeNode head) {
        if (head == null) {
            res.add(null);
        } else {
            res.add(String.valueOf(head.value));
            pres(res, head.left);
            pres(res, head.right);
        }
    }

    /**
     * 反序列化
     * @param preList
     * @return
     */
    public static TreeNode presb(Queue<String> preList){
        String poll = preList.poll();
        if (poll == null) {
            return null;
        }
        TreeNode head = new TreeNode(Integer.valueOf(poll));
        head.left = presb(preList);
        head.right = presb(preList);
        return head;
    }


    public static void main(String[] args) {
        TreeNode treeNode1 = new TreeNode(1);
        TreeNode treeNode2 = new TreeNode(2);
        TreeNode treeNode3 = new TreeNode(3);
        TreeNode treeNode4 = new TreeNode(4);
        TreeNode treeNode5 = new TreeNode(5);
        TreeNode treeNode6 = new TreeNode(6);
        TreeNode treeNode7 = new TreeNode(7);
        treeNode1.left = treeNode2;
        treeNode1.right = treeNode3;
        treeNode2.left = treeNode4;
        treeNode2.right = treeNode5;
        treeNode3.left = treeNode6;
        treeNode3.right  = treeNode7;

//        midSort(treeNode1);
//        System.out.println("--------------------");
//        leftSort(treeNode1);
//        System.out.println("--------------------");
//        rightSort(treeNode1);
        widthSort(treeNode1);
    }
}
